Clover icon

compiler

  1. Project Clover database Mon Jan 2 2023 15:09:37 MST
  2. Package com.google.javascript.jscomp

File LinkedFlowScope.java

 

Coverage histogram

../../../../img/srcFileCovDistChart9.png
54% of files have more coverage

Code metrics

76
137
26
4
495
298
72
0.53
5.27
6.5
2.77

Classes

Class Line # Actions
LinkedFlowScope 41 93 54 23
0.863905386.4%
LinkedFlowScope.FlowScopeJoinOp 242 7 2 0
1.0100%
LinkedFlowScope.LinkedFlowSlot 367 2 1 0
1.0100%
LinkedFlowScope.FlatFlowScopeCache 380 35 15 0
1.0100%
 

Contributing tests

This file is covered by 6743 tests. .

Source view

1    /*
2    * Copyright 2008 The Closure Compiler Authors.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10    * Unless required by applicable law or agreed to in writing, software
11    * distributed under the License is distributed on an "AS IS" BASIS,
12    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13    * See the License for the specific language governing permissions and
14    * limitations under the License.
15    */
16   
17    package com.google.javascript.jscomp;
18   
19    import com.google.common.base.Preconditions;
20    import com.google.common.collect.ImmutableMap;
21    import com.google.common.collect.Maps;
22    import com.google.common.collect.Sets;
23    import com.google.javascript.jscomp.Scope.Var;
24    import com.google.javascript.jscomp.type.FlowScope;
25    import com.google.javascript.rhino.Node;
26    import com.google.javascript.rhino.jstype.JSType;
27    import com.google.javascript.rhino.jstype.SimpleSlot;
28    import com.google.javascript.rhino.jstype.StaticScope;
29    import com.google.javascript.rhino.jstype.StaticSlot;
30   
31    import java.util.Iterator;
32    import java.util.Map;
33    import java.util.Set;
34   
35    /**
36    * A flow scope that tries to store as little symbol information as possible,
37    * instead delegating to its parents. Optimized for low memory use.
38    *
39    * @author nicksantos@google.com (Nick Santos)
40    */
 
41    class LinkedFlowScope implements FlowScope {
42    // The closest flow scope cache.
43    private final FlatFlowScopeCache cache;
44   
45    // The parent flow scope.
46    private final LinkedFlowScope parent;
47   
48    // The distance between this flow scope and the closest flat flow scope.
49    private int depth;
50   
51    static final int MAX_DEPTH = 250;
52   
53    // A FlatFlowScopeCache equivalent to this scope.
54    private FlatFlowScopeCache flattened;
55   
56    // Flow scopes assume that all their ancestors are immutable.
57    // So once a child scope is created, this flow scope may not be modified.
58    private boolean frozen = false;
59   
60    // The last slot defined in this flow instruction, and the head of the
61    // linked list of slots.
62    private LinkedFlowSlot lastSlot;
63   
 
64  418018 toggle private LinkedFlowScope(FlatFlowScopeCache cache,
65    LinkedFlowScope directParent) {
66  418018 this.cache = cache;
67  418018 if (directParent == null) {
68  133400 this.lastSlot = null;
69  133400 this.depth = 0;
70  133400 this.parent = cache.linkedEquivalent;
71    } else {
72  284618 this.lastSlot = directParent.lastSlot;
73  284618 this.depth = directParent.depth + 1;
74  284618 this.parent = directParent;
75    }
76    }
77   
 
78  133400 toggle LinkedFlowScope(FlatFlowScopeCache cache) {
79  133400 this(cache, null);
80    }
81   
 
82  284618 toggle LinkedFlowScope(LinkedFlowScope directParent) {
83  284618 this(directParent.cache, directParent);
84    }
85   
86    /** Gets the function scope for this flow scope. */
 
87  493278 toggle private Scope getFunctionScope() {
88  493278 return cache.functionScope;
89    }
90   
91    /** Whether this flows from a bottom scope. */
 
92  1894 toggle private boolean flowsFromBottom() {
93  1894 return getFunctionScope().isBottom();
94    }
95   
96    /**
97    * Creates an entry lattice for the flow.
98    */
 
99  131064 toggle public static LinkedFlowScope createEntryLattice(Scope scope) {
100  131064 return new LinkedFlowScope(new FlatFlowScopeCache(scope));
101    }
102   
 
103  67534 toggle @Override
104    public void inferSlotType(String symbol, JSType type) {
105  67534 Preconditions.checkState(!frozen);
106  67534 lastSlot = new LinkedFlowSlot(symbol, type, lastSlot);
107  67534 depth++;
108  67534 cache.dirtySymbols.add(symbol);
109    }
110   
 
111  48815 toggle @Override
112    public void inferQualifiedSlot(Node node, String symbol, JSType bottomType,
113    JSType inferredType) {
114  48815 Scope functionScope = getFunctionScope();
115  48815 if (functionScope.isLocal()) {
116  1241 if (functionScope.getVar(symbol) == null && !functionScope.isBottom()) {
117  806 functionScope.declare(symbol, node, bottomType, null);
118    }
119   
120  1241 inferSlotType(symbol, inferredType);
121    }
122    }
123   
 
124  1144 toggle @Override
125    public JSType getTypeOfThis() {
126  1144 return cache.functionScope.getTypeOfThis();
127    }
128   
 
129  2576 toggle @Override
130    public Node getRootNode() {
131  2576 return getFunctionScope().getRootNode();
132    }
133   
 
134  0 toggle @Override
135    public StaticScope<JSType> getParentScope() {
136  0 return getFunctionScope().getParentScope();
137    }
138   
139    /**
140    * Get the slot for the given symbol.
141    */
 
142  201995 toggle @Override
143    public StaticSlot<JSType> getSlot(String name) {
144  201995 if (cache.dirtySymbols.contains(name)) {
145  8767 for (LinkedFlowSlot slot = lastSlot;
146  31199 slot != null; slot = slot.parent) {
147  30073 if (slot.getName().equals(name)) {
148  7641 return slot;
149    }
150    }
151    }
152  194354 return cache.getSlot(name);
153    }
154   
 
155  0 toggle @Override
156    public StaticSlot<JSType> getOwnSlot(String name) {
157  0 throw new UnsupportedOperationException();
158    }
159   
 
160  285060 toggle @Override
161    public FlowScope createChildFlowScope() {
162  285060 frozen = true;
163   
164  285060 if (depth > MAX_DEPTH) {
165  442 if (flattened == null) {
166  442 flattened = new FlatFlowScopeCache(this);
167    }
168  442 return new LinkedFlowScope(flattened);
169    }
170   
171  284618 return new LinkedFlowScope(this);
172    }
173   
174    /**
175    * Iterate through all the linked flow scopes before this one.
176    * If there's one and only one slot defined between this scope
177    * and the blind scope, return it.
178    */
 
179  163 toggle @Override
180    public StaticSlot<JSType> findUniqueRefinedSlot(FlowScope blindScope) {
181  163 StaticSlot<JSType> result = null;
182   
183  163 for (LinkedFlowScope currentScope = this;
184  284 currentScope != blindScope;
185    currentScope = currentScope.parent) {
186  136 for (LinkedFlowSlot currentSlot = currentScope.lastSlot;
187  257 currentSlot != null &&
188    (currentScope.parent == null ||
189    currentScope.parent.lastSlot != currentSlot);
190    currentSlot = currentSlot.parent) {
191  136 if (result == null) {
192  108 result = currentSlot;
193  28 } else if (!currentSlot.getName().equals(result.getName())) {
194  15 return null;
195    }
196    }
197    }
198   
199  148 return result;
200    }
201   
202    /**
203    * Look through the given scope, and try to find slots where it doesn't
204    * have enough type information. Then fill in that type information
205    * with stuff that we've inferred in the local flow.
206    */
 
207  0 toggle @Override
208    public void completeScope(StaticScope<JSType> staticScope) {
209  0 Scope scope = (Scope) staticScope;
210  0 for (Iterator<Var> it = scope.getVars(); it.hasNext();) {
211  0 Var var = it.next();
212  0 if (var.isTypeInferred()) {
213  0 JSType type = var.getType();
214  0 if (type == null || type.isUnknownType()) {
215  0 JSType flowType = getSlot(var.getName()).getType();
216  0 var.setType(flowType);
217    }
218    }
219    }
220    }
221   
222    /**
223    * Remove flow scopes that add nothing to the flow.
224    */
225    // NOTE(nicksantos): This function breaks findUniqueRefinedSlot, because
226    // findUniqueRefinedSlot assumes that this scope is a direct descendant
227    // of blindScope. This is not necessarily true if this scope has been
228    // optimize()d and blindScope has not. This should be fixed. For now,
229    // we only use optimize() where we know that we won't have to do
230    // a findUniqueRefinedSlot on it.
 
231  673185 toggle @Override
232    public LinkedFlowScope optimize() {
233  673185 LinkedFlowScope current;
234  673185 for (current = this;
235  898490 current.parent != null &&
236    current.lastSlot == current.parent.lastSlot;
237    current = current.parent) {}
238  673185 return current;
239    }
240   
241    /** Join the two FlowScopes. */
 
242    static class FlowScopeJoinOp extends JoinOp.BinaryJoinOp<FlowScope> {
 
243  5912 toggle @SuppressWarnings("unchecked")
244    @Override
245    public FlowScope apply(FlowScope a, FlowScope b) {
246    // To join the two scopes, we have to
247  5912 LinkedFlowScope linkedA = (LinkedFlowScope) a;
248  5912 LinkedFlowScope linkedB = (LinkedFlowScope) b;
249  5912 linkedA.frozen = true;
250  5912 linkedB.frozen = true;
251  5912 if (linkedA.optimize() == linkedB.optimize()) {
252  4018 return linkedA.createChildFlowScope();
253    }
254  1894 return new LinkedFlowScope(new FlatFlowScopeCache(linkedA, linkedB));
255    }
256    }
257   
 
258  218753 toggle @Override
259    public boolean equals(Object other) {
260  218753 if (other instanceof LinkedFlowScope) {
261  218753 LinkedFlowScope that = (LinkedFlowScope) other;
262  218753 if (this.optimize() == that.optimize()) {
263  183 return true;
264    }
265   
266    // If two flow scopes are in the same function, then they could have
267    // two possible function scopes: the real one and the BOTTOM scope.
268    // If they have different function scopes, we *should* iterate through all
269    // the variables in each scope and compare. However, 99.9% of the time,
270    // they're not equal. And the other .1% of the time, we can pretend
271    // they're equal--this just means that data flow analysis will have
272    // to propagate the entry lattice a little bit further than it
273    // really needs to. Everything will still come out ok.
274  218570 if (this.getFunctionScope() != that.getFunctionScope()) {
275  217980 return false;
276    }
277   
278  590 if (cache == that.cache) {
279    // If the two flow scopes have the same cache, then we can check
280    // equality a lot faster: by just looking at the "dirty" elements
281    // in the cache, and comparing them in both scopes.
282  54 for (String name : cache.dirtySymbols) {
283  72 if (diffSlots(getSlot(name), that.getSlot(name))) {
284  48 return false;
285    }
286    }
287   
288  6 return true;
289    }
290   
291  536 Map<String, StaticSlot<JSType>> myFlowSlots = allFlowSlots();
292  536 Map<String, StaticSlot<JSType>> otherFlowSlots = that.allFlowSlots();
293   
294  536 for (StaticSlot<JSType> slot : myFlowSlots.values()) {
295  624 if (diffSlots(slot, otherFlowSlots.get(slot.getName()))) {
296  136 return false;
297    }
298  488 otherFlowSlots.remove(slot.getName());
299    }
300  400 for (StaticSlot<JSType> slot : otherFlowSlots.values()) {
301  96 if (diffSlots(slot, myFlowSlots.get(slot.getName()))) {
302  96 return false;
303    }
304    }
305  304 return true;
306    }
307  0 return false;
308    }
309   
310    /**
311    * Determines whether two slots are meaningfully different for the
312    * purposes of data flow analysis.
313    */
 
314  792 toggle private boolean diffSlots(StaticSlot<JSType> slotA,
315    StaticSlot<JSType> slotB) {
316  792 boolean aIsNull = slotA == null || slotA.getType() == null;
317  792 boolean bIsNull = slotB == null || slotB.getType() == null;
318  792 if (aIsNull && bIsNull) {
319  18 return false;
320  774 } else if (aIsNull ^ bIsNull) {
321  120 return true;
322    }
323   
324    // Both slots and types must be non-null.
325  654 return slotA.getType().differsFrom(slotB.getType());
326    }
327   
328    /**
329    * Gets all the symbols that have been defined before this point
330    * in the current flow. Does not return slots that have not changed during
331    * the flow.
332    *
333    * For example, consider the code:
334    * <code>
335    * var x = 3;
336    * function f() {
337    * var y = 5;
338    * y = 6; // FLOW POINT
339    * var z = y;
340    * return z;
341    * }
342    * </code>
343    * A FlowScope at FLOW POINT will return a slot for y, but not
344    * a slot for x or z.
345    */
 
346  5302 toggle private Map<String, StaticSlot<JSType>> allFlowSlots() {
347  5302 Map<String, StaticSlot<JSType>> slots = Maps.newHashMap();
348  5302 for (LinkedFlowSlot slot = lastSlot;
349  74399 slot != null; slot = slot.parent) {
350  69097 if (!slots.containsKey(slot.getName())) {
351  67591 slots.put(slot.getName(), slot);
352    }
353    }
354   
355  5302 for (Map.Entry<String, StaticSlot<JSType>> symbolEntry : cache.symbols.entrySet()) {
356  1179852 if (!slots.containsKey(symbolEntry.getKey())) {
357  1179265 slots.put(symbolEntry.getKey(), symbolEntry.getValue());
358    }
359    }
360   
361  5302 return slots;
362    }
363   
364    /**
365    * A static slot that can be used in a linked list.
366    */
 
367    private static class LinkedFlowSlot extends SimpleSlot {
368    final LinkedFlowSlot parent;
369   
 
370  67534 toggle LinkedFlowSlot(String name, JSType type, LinkedFlowSlot parent) {
371  67534 super(name, type, true);
372  67534 this.parent = parent;
373    }
374    }
375   
376    /**
377    * A map that tries to cache as much symbol table information
378    * as possible in a map. Optimized for fast lookup.
379    */
 
380    private static class FlatFlowScopeCache {
381    // The Scope for the entire function or for the global scope.
382    private final Scope functionScope;
383   
384    // The linked flow scope that this cache represents.
385    private final LinkedFlowScope linkedEquivalent;
386   
387    // All the symbols defined before this point in the local flow.
388    // May not include lazily declared qualified names.
389    private Map<String, StaticSlot<JSType>> symbols = Maps.newHashMap();
390   
391    // Used to help make lookup faster for LinkedFlowScopes by recording
392    // symbols that may be redefined "soon", for an arbitrary definition
393    // of "soon". ;)
394    //
395    // More rigorously, if a symbol is redefined in a LinkedFlowScope,
396    // and this is the closest FlatFlowScopeCache, then that symbol is marked
397    // "dirty". In this way, we don't waste time looking in the LinkedFlowScope
398    // list for symbols that aren't defined anywhere nearby.
399    final Set<String> dirtySymbols = Sets.newHashSet();
400   
401    // The cache at the bottom of the lattice.
 
402  131064 toggle FlatFlowScopeCache(Scope functionScope) {
403  131064 this.functionScope = functionScope;
404  131064 symbols = ImmutableMap.of();
405  131064 linkedEquivalent = null;
406    }
407   
408    // A cache in the middle of a long scope chain.
 
409  442 toggle FlatFlowScopeCache(LinkedFlowScope directParent) {
410  442 FlatFlowScopeCache cache = directParent.cache;
411   
412  442 functionScope = cache.functionScope;
413  442 symbols = directParent.allFlowSlots();
414  442 linkedEquivalent = directParent;
415    }
416   
417    // A cache at the join of two scope chains.
 
418  1894 toggle FlatFlowScopeCache(LinkedFlowScope joinedScopeA,
419    LinkedFlowScope joinedScopeB) {
420  1894 linkedEquivalent = null;
421   
422    // Always prefer the "real" function scope to the faked-out
423    // bottom scope.
424  1894 functionScope = joinedScopeA.flowsFromBottom() ?
425    joinedScopeB.getFunctionScope() : joinedScopeA.getFunctionScope();
426   
427  1894 Map<String, StaticSlot<JSType>> slotsA = joinedScopeA.allFlowSlots();
428  1894 Map<String, StaticSlot<JSType>> slotsB = joinedScopeB.allFlowSlots();
429   
430  1894 symbols = slotsA;
431   
432    // There are 5 different join cases:
433    // 1) The type is declared in joinedScopeA, not in joinedScopeB,
434    // and not in functionScope. Just use the one in A.
435    // 2) The type is declared in joinedScopeB, not in joinedScopeA,
436    // and not in functionScope. Just use the one in B.
437    // 3) The type is declared in functionScope and joinedScopeA, but
438    // not in joinedScopeB. Join the two types.
439    // 4) The type is declared in functionScope and joinedScopeB, but
440    // not in joinedScopeA. Join the two types.
441    // 5) The type is declared in joinedScopeA and joinedScopeB. Join
442    // the two types.
443  1894 Set<String> symbolNames = Sets.newHashSet(symbols.keySet());
444  1894 symbolNames.addAll(slotsB.keySet());
445   
446  1894 for (String name : symbolNames) {
447  31319 StaticSlot<JSType> slotA = slotsA.get(name);
448  31319 StaticSlot<JSType> slotB = slotsB.get(name);
449   
450  31319 JSType joinedType = null;
451  31319 if (slotB == null || slotB.getType() == null) {
452  668 StaticSlot<JSType> fnSlot
453    = joinedScopeB.getFunctionScope().getSlot(name);
454  668 JSType fnSlotType = fnSlot == null ? null : fnSlot.getType();
455  668 if (fnSlotType == null) {
456    // Case #1 -- already inserted.
457    } else {
458    // Case #3
459  545 joinedType = slotA.getType().getLeastSupertype(fnSlotType);
460    }
461  30651 } else if (slotA == null || slotA.getType() == null) {
462  291 StaticSlot<JSType> fnSlot
463    = joinedScopeA.getFunctionScope().getSlot(name);
464  291 JSType fnSlotType = fnSlot == null ? null : fnSlot.getType();
465  291 if (fnSlotType == null) {
466    // Case #2
467  73 symbols.put(name, slotB);
468    } else {
469    // Case #4
470  218 joinedType = slotB.getType().getLeastSupertype(fnSlotType);
471    }
472    } else {
473    // Case #5
474  30360 joinedType =
475    slotA.getType().getLeastSupertype(slotB.getType());
476    }
477   
478  31319 if (joinedType != null) {
479  31123 symbols.put(name, new SimpleSlot(name, joinedType, true));
480    }
481    }
482    }
483   
484    /**
485    * Get the slot for the given symbol.
486    */
 
487  194354 toggle public StaticSlot<JSType> getSlot(String name) {
488  194354 if (symbols.containsKey(name)) {
489  29510 return symbols.get(name);
490    } else {
491  164844 return functionScope.getSlot(name);
492    }
493    }
494    }
495    }
  • Report generated by OpenClover v 4.4.1 on Mon Jan 2 2023 15:17:08 MST using coverage data from Mon Jan 2 2023 15:16:37 MST.
  • OpenClover is free and open-source software.